package com.gitee.huxing.algorithmic.daily;

import java.lang.reflect.AnnotatedType;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Description: 733. 图像渲染
 * 有一幅以m x n的二维整数数组表示的图画image，其中image[i][j]表示该图画的像素值大小。
 *
 * 你也被给予三个整数 sr , sc 和 newColor 。你应该从像素image[sr][sc]开始对图像进行 上色填充 。
 *
 * 为了完成 上色工作 ，从初始像素开始，记录初始坐标的 上下左右四个方向上 像素值与初始坐标相同的相连像素点，
 * 接着再记录这四个方向上符合条件的像素点与他们对应 四个方向上 像素值与初始坐标相同的相连像素点，……，重复该过程。
 * 将所有有记录的像素点的颜色值改为newColor。
 *
 * 最后返回 经过上色渲染后的图像。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/flood-fill
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @ProjectName: algorithmic-pactice
 * @Package: FloodFill
 * @ClassName: FloodFill
 * @Author: huxingmale
 * @DateTime: 2022-05-16 9:39
 */
public class FloodFill {
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};

    public static void main(String[] args) {
        int[][] image = new int[][]{ {1,1,1},{1,1,0},{1,0,1}};
        Arrays.stream(floodFill(image, 1, 1, 2)).forEach(x -> {
            System.out.print(Arrays.toString(x));
        });
        System.out.println();
    }

    public static int[][] floodFill(int[][] image, int sr, int sc, int newColor){
        // 获取当前位置颜色
        int currColor = image[sr][sc];
        // 判断颜色是否相同，相同不需要渲染
        if (currColor == newColor){
            return image;
        }
        int n = image.length, m = image[0].length;
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[]{sr, sc});
        image[sr][sc] = newColor;
        while (!queue.isEmpty()){
            int[] cell = queue.poll();
            int x = cell[0], y = cell[1];
            for (int i = 0; i < 4; i++){
                int mx = x + dx[i], my = y + dy[i];
                if (mx >= 0 && mx < n && my >= 0 && my < m && image[mx][my] == currColor){
                    queue.offer(new int[]{mx, my});
                    image[mx][my] = newColor;
                }
            }
        }
        return image;
    }
}
